package com.llb666.java.leetcode;

import java.util.Arrays;

/**
 * 整形数组nums,在数组中找到三个数乘积最大，并输出乘积
 * Created by 斌~
 * 2021/4/27 16:27
 */
public class 三个数的最大乘积 {

    public static void main(String[] args) {
        int [] arr = {1,2,3,4,5,6};
        int maxMultiply = sort(arr);
        System.out.println(maxMultiply);

        int maxMin = getMaxMin(arr);
        System.out.println(maxMin);
    }

    /**
     * 排序算法计算
     * @param arr 数组
     * @return 最大乘积
     */
    private static int sort(int[] arr){
        //从小到大排序
        Arrays.sort(arr);
        //考虑正负数的情况，要使得三个数乘积，要么两个最小负数乘以最大值，要么最大的三个值乘积
        int n  = arr.length;
        return Math.max(arr[0]*arr[1]*arr[n-1],
                arr[n-1]*arr[n-2]*arr[n-3]);
    }

    /**
     * 线性扫描方法：从sort方法的启示，找到最小的两个值，以及最大的三个数值即可
     * @param arr 数组
     * @return 最大乘积
     */
    private static int getMaxMin(int[] arr){
       //定义最小的两个值
       int min1 = Integer.MAX_VALUE,min2=Integer.MAX_VALUE;
       // 定义最大的三个值
       int max1 = Integer.MIN_VALUE,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;
       for (int x : arr){
           if(x<min1){// x < 最小
               min2 = min1;
               min1 = x;
           }else if(x<min2){ // 最小 < x < 第二小
               min2 = x;
           }
           if(x>max1){ //x > 最大
               max3 = max2;
               max2 = max1;
               max1 = x;
           }else if(x>max2){ // 最大 >  x> 第二大
               max3 =max2;
               max2 = x;
           }else if(x>max3){ // 第二大 >  x> 第三大
               max3 =x;
           }
       }
       return Math.max(min1*min2*max1,max1*max2*max3);
    }
}
